package com.drico.operations.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;

import com.drico.exceptions.NotFoudEdgeException;
import com.drico.grafo.Edge;
import com.drico.grafo.Grafo;
import com.drico.grafo.Vertex;
import com.drico.operations.GrafoHandler;

public class GrafoHandlerImpl implements GrafoHandler {
	
	private Grafo grafo;
	private Hashtable<String, Boolean> vis;
	private Vector<Vertex> path;
	private Vertex vi;
	private Vertex vf;
	private List<String> paths = new ArrayList<String>();
	private int stops;
	private Double distance;
	private double cicleDistance = Double.POSITIVE_INFINITY;
	
	public GrafoHandlerImpl(Grafo grafo){
		this.grafo = grafo;
	}
	
	public Grafo getGrafo() {
		return grafo;
	}

	public void setGrafo(Grafo grafo) {
		this.grafo = grafo;
	}

	//*************
	public Double distanceRoute(String route) throws NotFoudEdgeException {

		StringTokenizer st = new StringTokenizer(route, "-");
		Vertex vertex = grafo.getVertex(st.nextToken());
		return distance(vertex,st);		
	}

	private double distance(Vertex vertex, StringTokenizer edges) throws NotFoudEdgeException {
		double distance = 0;
		if (edges.hasMoreTokens()) {
			String next = edges.nextToken();
			distance += vertex.hasEdge(next) + distance(grafo.getVertex(next),edges);	
		}
		return distance;
	}
	//*************
	
	//*************
	public void computePaths(String start) {
		
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		
		grafo.cleanDistances();
		Vertex vertex = grafo.getVertex(start);
		vertex.setMinDistance(0);
		vertexQueue.add(vertex);

		while (!vertexQueue.isEmpty()) {
			Vertex u = vertexQueue.poll();

			// Visit each edge exiting u
			for (Edge e : u.getAdjacencies()) {
				Vertex v = e.getTarget();
				double weight = e.getWeight();
				double distanceThroughU = u.getMinDistance() + weight;
				if (distanceThroughU < v.getMinDistance()) {
					vertexQueue.remove(v);
					v.setMinDistance(distanceThroughU);
					v.setPrevious(u);
					vertexQueue.add(v);
				}
			}
		}
	}

	public List<Vertex> getShortestPathTo(Vertex target) {
		List<Vertex> path = new ArrayList<Vertex>();
		for (Vertex vertex = target; vertex != null; vertex = vertex.getPrevious())
			path.add(vertex);

		Collections.reverse(path);
		return path;
	}
	
	public void computePathsCicleDistance(String start, String end) {
		
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		
		grafo.cleanDistances();
		cicleDistance = Double.POSITIVE_INFINITY;
		
		Vertex vertex = grafo.getVertex(start);
		Vertex vertexF = grafo.getVertex(end);
		
		vertex.setMinDistance(0);
		vertexQueue.add(vertex);

		while (!vertexQueue.isEmpty()) {
			Vertex u = vertexQueue.poll();

			// Visit each edge exiting u
			for (Edge e : u.getAdjacencies()) {
				Vertex v = e.getTarget();
				double weight = e.getWeight();
				double distanceThroughU = u.getMinDistance() + weight;
				
				if(v.equals(vertexF) && distanceThroughU < cicleDistance)
					cicleDistance = distanceThroughU;
				
				if (distanceThroughU < v.getMinDistance()) {
					vertexQueue.remove(v);
					
					v.setMinDistance(distanceThroughU);
					v.setPrevious(u);
					vertexQueue.add(v);
				}
			}
		}
	}

	
	public double getCicleMinDistance() {
		return cicleDistance;
	}
	
	private void inicialize(){
		vis = new Hashtable<String, Boolean>();
		Iterator<String> it = grafo.getVertexs().keySet().iterator();
		while (it.hasNext()) vis.put(it.next(), false);
	}
	
	
	public List<String> seachByMaxStops(String start, String end, int stops){
		
		this.stops = stops;
		vi = grafo.getVertex(start);
		vf = grafo.getVertex(end);
		path = new Vector<Vertex>();
		paths = new ArrayList<String>();
		inicialize();
		
		seachPath(vi);
		return paths;
	}
	
	private void seachPath(Vertex v){
			
		Iterator<Vertex> it = grafo.getVertexs().values().iterator();
		while (it.hasNext()) {
			Vertex k = it.next();
			
			if(v.isVisitable(k) && !vis.get(k.getName())){
				addVertex(k);
				if (k.equals(vf)){
					if(path.size() <= stops)
						paths.add(writePath(path));
				} else
					seachPath(k);
				deleteVertex(k);
			}
		}	
		
	}

	private void deleteVertex(Vertex k) {
		path.remove(k);
		vis.put(k.getName(), false);
	}

	private String writePath(Vector<Vertex> vetexs) {
		String s = vi.getName();
		for (int i = 0; i < vetexs.size(); i++) {
			s += "-" + vetexs.get(i).getName();
		}
		return s;
	}

	private void addVertex(Vertex k) {
		path.add(k);
		vis.put(k.getName(), true);
	}
	
	public List<String> searchByStop(String start, String end, int paradas){
		
		this.stops = paradas;
		vi = grafo.getVertex(start);
		vf = grafo.getVertex(end);
		path = new Vector<Vertex>();
		paths = new ArrayList<String>();
		inicialize();
		
		searchPathByStop(vi);
		return paths;
	}
	
	private void searchPathByStop(Vertex v){
			
		Iterator<Vertex> it = grafo.getVertexs().values().iterator();
		while (it.hasNext()) {
			Vertex k = it.next();
			
			if(v.isVisitable(k) && !vis.get(k.getName())){
				addVertex(k);
				
				if (k.equals(vf)){
						vis.put(k.getName(), false);
						
						Iterator<String> itNames = k.getAdjacenciesName().iterator();
						while(itNames.hasNext())
							vis.put(itNames.next(), false);						
				}	
				
				if(path.size() == stops){
					 if(path.lastElement().getName().equals(vf.getName()))
						paths.add(writePath(path));
				} else
					searchPathByStop(k);
				
				deleteVertex(k);
			}
		}	
		
	}
	
	public List<String> seachByDistance(String start, String end, double distancia) {
		this.distance = distancia;
		vi = grafo.getVertex(start);
		vf = grafo.getVertex(end);
		path = new Vector<Vertex>();
		paths = new ArrayList<String>();
		inicialize();
		
		seachPathByDistance(vi);
		return paths;
	}
	
	private void seachPathByDistance(Vertex v){
		
		Iterator<Vertex> it = grafo.getVertexs().values().iterator();
		while (it.hasNext()) {
			Vertex k = it.next();
			
			if(v.isVisitable(k) && !vis.get(k.getName())){
				addVertex(k);
				
				if (k.equals(vf)){
						vis.put(k.getName(), false);
						Iterator<String> itNames = k.getAdjacenciesName().iterator();
						while(itNames.hasNext())
							vis.put(itNames.next(), false);						
				}	
				
				if(distanceFrom())
					 if(path.lastElement().getName().equals(vf.getName()))
						paths.add(writePath(path));
				else
					seachPathByDistance(k);
				
				deleteVertex(k);
			}
		}	
		
	}
	
	public boolean distanceFrom(){
		double dis = 0d;
		try {
			dis += distanceRoute(writePath(path));
		} catch (NotFoudEdgeException e) {
			e.printStackTrace();
		}		
		return dis <= this.distance;
	}

	//*************
}
